//在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“
//房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 
//
// 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 
//
// 示例 1: 
//
// 输入: [3,2,3,null,3,null,1]
//
//     3
//    / \
//   2   3
//    \   \ 
//     3   1
//
//输出: 7 
//解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 
//
// 示例 2: 
//
// 输入: [3,4,5,1,3,null,1]
//
//     3
//    / \
//   4   5
//  / \   \ 
// 1   3   1
//
//输出: 9
//解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
// 
// Related Topics 树 深度优先搜索 动态规划 二叉树 
// 👍 892 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;

public class HouseRobberIii {
    public static void main(String[] args) {
        Solution solution = new HouseRobberIii().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 当前节点偷 = 左右儿子能偷到的钱最大值的总和+当前节点的值   （能偷到，指的是可偷可不偷）
    // 当前节点不偷 = 左右儿子偷的钱的总和
    // 行为动态规划，一般就将行为定义为状态，在这里的行为就是偷东西，对应状态就是偷和不偷
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0],res[1]);
    }
    public int[] dfs(TreeNode root){
        if (root==null){
            return new int[]{0,0};
        }
        int[] lefts = dfs(root.left);
        // 左儿子不偷
        int left_noS = lefts[0];
        // 左儿子偷
        int left_S = lefts[1];
        int[] rights = dfs(root.right);
        // 右儿子不偷
        int right_noS = rights[0];
        // 右儿子偷
        int right_S = rights[1];

        // 当前节点不偷,偷
        return new int[]{Math.max(left_S,left_noS)+Math.max(right_S,right_noS),left_noS+right_noS+root.val};
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}